from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        m, n = len(pizza), len(pizza[0])

        # 计算从右下角到任一点的苹果数量（后缀频数）
        suffix = [[0] * n for _ in range(m)]
        suffix[-1][-1] = (1 if pizza[-1][-1] == "A" else 0)
        for i in range(m - 2, -1, -1):
            suffix[i][-1] = suffix[i + 1][-1] + (1 if pizza[i][-1] == "A" else 0)
        for j in range(n - 2, -1, -1):
            suffix[-1][j] = suffix[-1][j + 1] + (1 if pizza[-1][j] == "A" else 0)
        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                suffix[i][j] = (suffix[i][j + 1] + suffix[i + 1][j] - suffix[i + 1][j + 1] +
                                (1 if pizza[i][j] == "A" else 0))

        # for row in suffix:
        #     print(row)

        # 定义状态矩阵：dp[i][j][v] = 剩下的左上角是(i,j)，已经切了v刀时的方案数
        dp = [[[0] * n for _ in range(m)] for _ in range(k)]
        dp[0][0][0] = 1

        # 状态转移
        for v in range(1, k):
            # 水平切
            for i1 in range(1, m):
                for i2 in range(i1):
                    for j in range(n):
                        if suffix[i2][j] - suffix[i1][j] > 0 and suffix[i1][j] > 0:  # 保证两部分都有苹果
                            dp[v][i1][j] = (dp[v][i1][j] + dp[v - 1][i2][j]) % MOD

            # 垂直切
            for j1 in range(1, n):
                for j2 in range(j1):
                    for i in range(m):
                        if suffix[i][j2] - suffix[i][j1] > 0 and suffix[i][j1] > 0:  # 保证两部分都有苹果
                            dp[v][i][j1] = (dp[v][i][j1] + dp[v - 1][i][j2]) % MOD

        ans = 0
        for i in range(m):
            for j in range(n):
                ans += dp[-1][i][j]
        return ans % MOD


if __name__ == "__main__":
    # 3
    print(Solution().ways(pizza=["A..",
                                 "AAA",
                                 "..."], k=3))

    # 1
    print(Solution().ways(pizza=["A..",
                                 "AA.",
                                 "..."], k=3))

    # 1
    print(Solution().ways(pizza=["A..",
                                 "A..",
                                 "..."], k=1))
